Flash memory may be designed using single-level cells, which store a single bit of information in each memory cell, or as multi-level cells, which store multiple bits of information in each memory cell. In general, single-level cells have higher endurance than multi-level cells. However, multi-level cells provide higher storage density than single-level cells. A multi-level cell memory (e.g., a flash memory) is comprised of multi-level cells, each of which is able to store multiple charge states or levels. Each of the charge states is associated with a memory element bit pattern. A multi-level cell memory is configurable to store multiple threshold voltage levels (Vt).
A multi-level cell memory is able to store more than one bit of data based upon the number of charge states. For example, a multi-level cell memory that can store four charge states (or four Vt levels) can store two bits of data, a multilevel cell memory that can store eight charge states (or eight Vt levels) can store three bits of data, and a multilevel cell that can store sixteen charge states can store four bits of data. For each of the n-bit multi-level cell memories, various memory element bit patterns can be associated with each of the different charge states. A reference voltage may separate the various charge states. For example, a first voltage reference may separate level 3 and level 2, a second voltage reference may separate level 2 from level 1, and a third reference voltage may separate level 1 from level 0.
Binary information may be mapped directly to a single-level cell memory. However, multi-level cells require memory mapping operations to map binary information onto the number of levels in the multi-level cells. A binary to ternary mapping is a function which takes binary data and maps it to ternary symbols. A typical binary to ternary mapping first obtains a decimal representation of the binary string and then maps this decimal number to its ternary representation. The compression obtained by this mapping is close to the theoretical limit. For example, 1 kilobyte bits (i.e., 8192 bits) can be mapped to 5169 ternary symbols. The compression obtained is 1.5848 which is close to the theoretical limit. The theoretical storage limit of each 3-level memory cell is Log 2(3)=1.5849 bits
One problem with this typical binary to ternary mapping is that it suffers from error propagation. Consider a binary string “000 . . . 001111” to be stored. The decimal representation of this string is 15 and the ternary representation is “000 . . . 00120”. This ternary string stored (e.g., to a NAND flash memory) as level information in the cells is read back. Since there are errors when reading from the memory (e.g., NAND flash memory), say “0000 . . . 00121” is read back (i.e., the last level 0 is readout as level 1). The binary representation for this noisy readout is “000 . . . 0010000”. Hence, an error of a single level translates to 5 bits in read out error. The typical mapping has an error propagation by a factor of 3.5, which means that the bit error rate is 3.5 times the level error rate.